package pers.qianyu.month_202101.date_20210123;

/**
 * 74. 搜索二维矩阵
 * https://leetcode-cn.com/problems/search-a-2d-matrix/
 *
 * @author mizzle rain
 * @date 2021-01-23 17:07
 */
public class SearchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int h = matrix.length, w = matrix[0].length;
        int left = 0, right = h * w - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (matrix[mid / w][mid % w] >= target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return matrix[left / w][left % w] == target;
    }
}
